﻿#ifndef METHOD_H
#define METHOD_H

#include <queue>
#include "Board.h"
#include<vector>
#include <mutex>
using std::mutex;
mutex mtx;

/// 里面写了一个广搜的算法, 用来判断长链, 环和短链等等

struct {
	bool operator()(Step a, Step b)
	{
		if (a.dir > b.dir)
			return true;
		else if (a.dir == b.dir)
		{
			if (a.x > b.x)
				return true;
			else if (a.x == b.x)
			{
				if (a.y > b.y)
					return true;
				else
					return false;
			}
			else
				return false;
		}
		else
			return false;
	}
}step_temp;


typedef struct pair {
	int x;
	int y;
};

const int N = 5;
int dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, -1, 0, 1 };//方向数组
bool st[N][N];//判重数组

//对当前格子判断是否存在长链
void bfs_(int x, int y, Board* board, int& long_count, std::vector<std::vector<Step>>& long_chain)
{
	std::queue<pair> q;
	if (board->get_line_count(x, y) != 2)
	{
		return;
	}
	q.push({ x, y });
	st[x][y] = true;
	int length_chain = 0;
	while (!q.empty())
	{

		auto t = q.front();//取出队头
		q.pop();
		st[t.x][t.y] = true;
		if (board->get_line_count(t.x, t.y) != 2)
		{
			continue;
		}
		for (int i = 0; i < 4; i++)
		{
			int a = t.x + dx[i];
			int	b = t.y + dy[i];
			if (st[a][b])
			{
				continue;
			}
			if (i == 0 && board->line[0][t.x + 1][t.y] == 0)
			{
				//把这个长链的可下位置装进去
				Step step = { 0,t.x + 1,t.y };
				long_chain[long_count].push_back(step);
				if ((a >= 0 && a <= 4 && b >= 0 && b <= 4) && board->get_line_count(a, b) == 2)
				{
					q.push({ a, b });
				}
				length_chain++;//长链长度 ++ ；
			}
			if (i == 1 && board->line[1][t.y][t.x] == 0)
			{
				//把这个长链的可下位置装进去
				Step step = { 1,t.y,t.x };
				long_chain[long_count].push_back(step);
				if ((a >= 0 && a <= 4 && b >= 0 && b <= 4) && board->get_line_count(a, b) == 2)
				{
					q.push({ a, b });
				}
				length_chain++;//长链长度 ++ 
			}
			if (i == 2 && board->line[0][t.x][t.y] == 0)
			{
				//把这个长链的可下位置装进去
				Step step = { 0,t.x,t.y };
				long_chain[long_count].push_back(step);
				if ((a >= 0 && a <= 4 && b >= 0 && b <= 4) && board->get_line_count(a, b) == 2)
				{
					q.push({ a, b });
				}
				length_chain++;//长链长度 ++ 
			}
			if (i == 3 && board->line[1][t.y + 1][t.x] == 0)
			{
				//把这个长链的可下位置装进去
				Step step = { 1,t.y + 1,t.x };
				long_chain[long_count].push_back(step);
				if ((a >= 0 && a <= 4 && b >= 0 && b <= 4) && board->get_line_count(a, b) == 2)
				{
					q.push({ a, b });
				}
				length_chain++;//长链长度 ++ 
			}
		}
	}
	//这里判断是否满足长链的条件否则pop出去
	long_count++;
	if (length_chain < 3)
	{
		long_chain.erase(long_chain.begin() + long_count - 1);
		long_count--;
	}
}

//测试新的BFS
void bfs__(int x, int y, Board* board, int& long_count, std::vector<std::vector<Step>>& long_chain)
{
	std::queue<pair> q;
	if (board->get_line_count(x, y) != 2)
	{
		return;
	}
	q.push({ x, y });
	st[x][y] = true;
	int length_chain = 0;
	int count = 1;
	while (!q.empty())
	{
		auto t = q.front();
		q.pop();
		st[t.x][t.y] = true;
		if (board->line[0][t.x][t.y] == 0)
		{
			Step step = { 0,t.x,t.y };
			int find_flag = 0;
			if (!long_chain[long_count].empty())
			{
				for (int j = 0; j < long_chain[long_count].size(); j++)
				{
					if (step == long_chain[long_count][j])
					{
						find_flag = 1;
						break;
					}
				}
				if (find_flag == 0)
				{
					long_chain[long_count].emplace_back(step);
					length_chain++;
					long_chain[long_count].shrink_to_fit();
				}
			}
			else
			{
				long_chain[long_count].emplace_back(step);
				length_chain++;
				long_chain[long_count].shrink_to_fit();
			}
		}
		if (board->line[0][t.x + 1][t.y] == 0)
		{
			Step step = { 0,t.x + 1,t.y };
			int find_flag = 0;
			if (!long_chain[long_count].empty())
			{
				for (int j = 0; j < long_chain[long_count].size(); j++)
				{
					if (step == long_chain[long_count][j])
					{
						find_flag = 1;
						break;
					}
				}
				if (find_flag == 0)
				{
					long_chain[long_count].emplace_back(step);
					length_chain++;
					long_chain[long_count].shrink_to_fit();
				}
			}
			else
			{
				long_chain[long_count].emplace_back(step);
				length_chain++;
				long_chain[long_count].shrink_to_fit();
			}
		}
		if (board->line[1][t.y][t.x] == 0)
		{
			Step step = { 1,t.y,t.x };
			int find_flag = 0;
			if (!long_chain[long_count].empty())
			{
				for (int j = 0; j < long_chain[long_count].size(); j++)
				{
					if (step == long_chain[long_count][j])
					{
						find_flag = 1;
						break;
					}
				}
				if (find_flag == 0)
				{
					long_chain[long_count].emplace_back(step);
					length_chain++;
					long_chain[long_count].shrink_to_fit();
				}
			}
			else
			{
				long_chain[long_count].emplace_back(step);
				length_chain++;
				long_chain[long_count].shrink_to_fit();
			}
		}
		if (board->line[1][t.y + 1][t.x] == 0)
		{
			Step step = { 1,t.y + 1,t.x };
			int find_flag = 0;
			if (!long_chain[long_count].empty())
			{
				for (int j = 0; j < long_chain[long_count].size(); j++)
				{
					if (step == long_chain[long_count][j])
					{
						find_flag = 1;
						break;
					}
				}
				if (find_flag == 0)
				{
					long_chain[long_count].emplace_back(step);
					length_chain++;
					long_chain[long_count].shrink_to_fit();
				}
			}
			else
			{
				long_chain[long_count].emplace_back(step);
				length_chain++;
				long_chain[long_count].shrink_to_fit();
			}
		}
		if (board->get_line_count(t.x, t.y) != 2)
		{
			continue;
		}
		for (int i = 0; i < 4; i++)
		{
			int a = t.x + dx[i];
			int	b = t.y + dy[i];
			if (a < 0 || a >= 5 || b < 0 || b >= 5 || st[a][b] == true)
			{
				continue;
			}
			if (i == 0 && board->get_line_count(a, b) == 2 && board->line[0][t.x + 1][t.y] == 0)
			{
				q.push({ a,b });
				st[a][b] = true;
				count++;
			}
			if (i == 1 && board->get_line_count(a, b) == 2 && board->line[1][t.y][t.x] == 0)
			{
				q.push({ a,b });
				st[a][b] = true;
				count++;
			}
			if (i == 2 && board->get_line_count(a, b) == 2 && board->line[0][t.x][t.y] == 0)
			{
				q.push({ a,b });
				st[a][b] = true;
				count++;
			}
			if (i == 3 && board->get_line_count(a, b) == 2 && board->line[1][t.y + 1][t.x] == 0)
			{
				q.push({ a,b });
				st[a][b] = true;
				count++;
			}
		}

	}
	long_count++;
	if (length_chain < 2)
	{
		long_chain.erase(long_chain.begin() + long_count - 1);
		long_count--;
	}
}
std::vector<std::vector<Step>> chain_jug(Board* board)
{
	memset(st, false, sizeof(st));
	int long_count = 0;
	std::vector<std::vector<Step>> long_chain;
	long_chain.resize(60);
	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++)
		{
			//测试位
			bfs__(i, j, board, long_count, long_chain);
		}
	//将vector 的大小调整为适合的大小
	long_chain.resize(long_count);
	long_chain.shrink_to_fit();
	return long_chain;
}



int dx_loop[3] = { 0,1,1 };
int dy_loop[3] = { 1,0,1 };
bool st_loop[5][5];
bool is_circle;//true is loop



std::vector<Step> loop_jug(Board* board)
{
	int cnt = 0;//loop numbers
	//判重数组初始化
	memset(st_loop, false, sizeof(st_loop));
	std::vector<Step> loop_steps;
	for (int i = 0; i + 1 < 5; i++)
		for (int j = 0; j + 1 < 5; j++)
		{
			if (board->get_line_count(i, j) == 2 && board->line[0][i][j] == 1 && board->line[1][j][i] == 1)
			{
				is_circle = true;
				for (int k = 0; k < 3; k++)
				{
					int a = i + dx_loop[k];
					int b = j + dy_loop[k];
					if (board->get_line_count(a, b) != 2 || st_loop[a][b])
						is_circle = false;
					if (k == 0 && (board->get_line_count(a, b) != 2 || board->line[0][a][b] == 0 || board->line[1][b + 1][a] == 0))
						is_circle = false;
					if (k == 1 && (board->get_line_count(a, b) != 2 || board->line[0][a + 1][b] == 0 || board->line[1][b][a] == 0))
						is_circle = false;
					if (k == 2 && (board->get_line_count(a, b) != 2 || board->line[0][a + 1][b] == 0 || board->line[1][b + 1][a] == 0))
						is_circle = false;
				}
				if (is_circle)
				{
					Step step1 = { 1,j + 1,i };//上
					Step step2 = { 0,i + 1,j };//左
					Step step3 = { 1,j + 1,i + 1 };//下
					Step step4 = { 0,i + 1,j + 1 };//右
					loop_steps.push_back(step1);
					loop_steps.push_back(step2);
					loop_steps.push_back(step3);
					loop_steps.push_back(step4);
					loop_steps.shrink_to_fit();
					cnt++;
					st_loop[i][j] = true;
					st_loop[i][j + 1] = true;
					st_loop[i + 1][j] = true;
					st_loop[i + 1][j + 1] = true;
				}
			}
		}
	return loop_steps;
}



//判断双交
bool st_double[5][5];
int check_double(Board* board)
{
	memset(st_double, false, sizeof(st_double));
	int cnt = 0;
	int dx[4] = { 1,0,-1,0 };
	int dy[4] = { 0,-1,0,1 };
	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 5; j++)
		{
			for (int k = 0; k < 4; k++)
			{
				int a = i + dx[k];
				int b = j + dy[k];
				if (a < 0 || a >= 5 || b < 0 || b >= 5 || board->get_line_count(i, j) != 3 || st_double[a][b])
					continue;
				if (k == 0 && board->get_line_count(a, b) == 3 && board->line[0][i][j] == 0)
				{
					st_double[i][j] = true;
					st_double[a][b] = true;
					cnt++;
					break;
				}
				if (k == 1 && board->get_line_count(a, b) == 3 && board->line[1][j][i] == 0)
				{
					st_double[i][j] = true;
					st_double[a][b] = true;
					cnt++;
					break;
				}
				if (k == 2 && board->get_line_count(a, b) == 3 && board->line[0][i][j] == 0)
				{
					st_double[i][j] = true;
					st_double[a][b] = true;
					cnt++;
					break;
				}
				if (k == 3 && board->get_line_count(a, b) == 3 && board->line[0][i + 1][j] == 0)
				{
					st_double[i][j] = true;
					st_double[a][b] = true;
					cnt++;
					break;
				}
			}
		}
	}
	return cnt;
}



#endif // !METHOD_H


